﻿#define _CRT_SECURE_NO_WARNINGS 1

/*
回文链表，实际上只是将回文数存储在链表中
解决办法1：
// 时间复杂度O(n)
// 空间复杂度O(1)
//先找尾节点，找到尾看是否相同
//相同则利用长度差，确保双指针效率
解决办法2:
// 时间复杂度O(n)
// 空间复杂度O(n)
//哈希，先将一个链表的节点存入哈希桶
//然后遍历寻找
*/

//每日一题_07
//160. 相交链表
//https://leetcode.cn/problems/intersection-of-two-linked-lists/description/

//解决方法1
class Solution {
public:
    ListNode* getIntersectionNode(ListNode* headA, ListNode* headB)
    {
        struct ListNode* curA = headA;
        struct ListNode* curB = headB;

        int lenA = 1;
        int lenB = 1;
        //找尾结点
        while (curA->next)
        {
            lenA++;
            curA = curA->next;
        }

        while (curB->next)
        {
            lenB++;
            curB = curB->next;
        }

        if (curA != curB)
        {
            return NULL;
        }

        int n = abs(lenA - lenB);
        struct ListNode* longList = headA;
        struct ListNode* shortList = headB;

        if (lenB > lenA)
        {
            longList = headB;
            shortList = headA;
        }

        while (n--)
        {
            longList = longList->next;
        }

        while (longList != shortList)
        {
            longList = longList->next;
            shortList = shortList->next;
        }

        return longList;
    }
};

//解决办法2
class Solution {
public:
    ListNode* getIntersectionNode(ListNode* headA, ListNode* headB)
    {
        unordered_set<ListNode*> hash;
        ListNode* temp = headA;

        while (temp != nullptr)
        {
            hash.insert(temp);
            temp = temp->next;
        }

        temp = headB;
        while (temp != nullptr)
        {
            if (hash.count(temp))
            {
                return temp;
            }
            else
            {
                temp = temp->next;
            }
        }
        return nullptr;
    }
};